import copy


class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        flag_matrix = [[0 for _ in range(9)] for _ in range(9)]
        num_matrix = [[0 for _ in range(9)] for _ in range(9)]
        count = 0
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    num_matrix[i][j] = [i + 1 for i in range(9)]
                    flag_matrix[i][j] = 0
                else:
                    num_matrix[i][j] = int(board[i][j])
                    flag_matrix[i][j] = 1
                    count += 1

        def jie_shudu(num_matrix, flag_matrix, count):
            last_count = count
            while count < 81:
                for i in range(9):
                    for j in range(9):
                        if flag_matrix[i][j] == 0:
                            fangxing_matrix = []
                            heng = int(i / 3)
                            zong = int(j / 3)
                            for m in range(3):
                                for n in range(3):
                                    if flag_matrix[3 * heng + m][3 * zong + n] == 1:
                                        fangxing_matrix.append(num_matrix[3 * heng + m][3 * zong + n])
                            heng_matrix = []
                            zong_matrix = []
                            for m in range(9):
                                if flag_matrix[m][j] == 1:
                                    heng_matrix.append(num_matrix[m][j])
                                if flag_matrix[i][m] == 1:
                                    zong_matrix.append(num_matrix[i][m])
                            pro_list = []
                            for m in range(1, 10):
                                if m not in fangxing_matrix and m not in heng_matrix and m not in zong_matrix:
                                    pro_list.append(m)
                            if len(pro_list) == 1:
                                num_matrix[i][j] = pro_list[0]
                                flag_matrix[i][j] = 1
                                count += 1
                            else:
                                num_matrix[i][j] = pro_list
                if count == last_count:
                    break
                else:
                    last_count = count
            if count == 81:
                for i in range(9):
                    for j in range(9):
                        board[i][j] = str(num_matrix[i][j])
                return True
            else:
                for i in range(9):
                    for j in range(9):
                        if flag_matrix[i][j] == 0:
                            if len(num_matrix[i][j]) == 0:
                                return False
                            else:
                                for item in num_matrix[i][j]:
                                    new_num_matrix = copy.deepcopy(num_matrix)
                                    new_num_matrix[i][j] = item
                                    new_flag_matrix = copy.deepcopy(flag_matrix)
                                    new_flag_matrix[i][j] = 1
                                    flag = jie_shudu(new_num_matrix, new_flag_matrix, count + 1)
                                    if flag:
                                        return flag
                                return False

        jie_shudu(num_matrix, flag_matrix, count)
        return board


data = Solution()
# board = [[".", ".", "9", "7", "4", "8", ".", ".", "."], ["7", ".", ".", ".", ".", ".", ".", ".", "."],
#          [".", "2", ".", "1", ".", "9", ".", ".", "."], [".", ".", "7", ".", ".", ".", "2", "4", "."],
#          [".", "6", "4", ".", "1", ".", "5", "9", "."], [".", "9", "8", ".", ".", ".", "3", ".", "."],
#          [".", ".", ".", "8", ".", "3", ".", "2", "."], [".", ".", ".", ".", ".", ".", ".", ".", "6"],
#          [".", ".", ".", "2", "7", "5", "9", ".", "."]]
# board = [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."],
#          [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
#          ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
#          [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"],
#          [".", ".", ".", ".", "8", ".", ".", "7", "9"]]
board = [[".", ".", ".", "2", ".", ".", ".", "6", "3"], ["3", ".", ".", ".", ".", "5", "4", ".", "1"],
         [".", ".", "1", ".", ".", "3", "9", "8", "."], [".", ".", ".", ".", ".", ".", ".", "9", "."],
         [".", ".", ".", "5", "3", "8", ".", ".", "."], [".", "3", ".", ".", ".", ".", ".", ".", "."],
         [".", "2", "6", "3", ".", ".", "5", ".", "."], ["5", ".", "3", "7", ".", ".", ".", ".", "8"],
         ["4", "7", ".", ".", ".", "1", ".", ".", "."]]
print(data.solveSudoku(board))
